Total dominación romana {3}: la complejidad y algoritmo de tiempo lineal para árboles
Autores: Liu, Xinyue; Jiang, Huiqin; Wu, Pu; Shao, Zehui
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Total dominación romana {3}: la complejidad y algoritmo de tiempo lineal para árboles
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Grafo simple
Vértices aislados
Función de dominación total Romana {3}
Peso
Número de dominación total Romana {3}
NP-completo
Grafos planares
Grafos bipartitos cordales
Algoritmo de tiempo lineal
árboles
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Para un grafo simple sin vértices aislados, una función total de dominación Romana {3} (TR3DF) en es una función que tiene la propiedad de que (i) si ; (ii) si ; y (iii) cada vértice con tiene un vecino con para cada vértice . El peso de un TR3DF es la suma y el peso mínimo de una función total de dominación Romana {3} en se llama el número total de dominación Romana {3} denotado por . En este artículo, mostramos que el problema de dominación total Romana {3} es NP-completo para grafos planares y grafos bipartitos cordales. Finalmente, presentamos un algoritmo de tiempo lineal para calcular el valor de para árboles.
Descripción
Para un grafo simple sin vértices aislados, una función total de dominación Romana {3} (TR3DF) en es una función que tiene la propiedad de que (i) si ; (ii) si ; y (iii) cada vértice con tiene un vecino con para cada vértice . El peso de un TR3DF es la suma y el peso mínimo de una función total de dominación Romana {3} en se llama el número total de dominación Romana {3} denotado por . En este artículo, mostramos que el problema de dominación total Romana {3} es NP-completo para grafos planares y grafos bipartitos cordales. Finalmente, presentamos un algoritmo de tiempo lineal para calcular el valor de para árboles.